# -*- coding: utf-8 -*-
'''
and now something completely diferent...
'''
import sys
import math

# para que se possa medir os tempos de execução
import time

# para gerar listas preenchidas com números aleatórios
import random

def max_heapify(A, i):
    global heapsize

    l = 2 * i
    r = 2 * i + 1
    
    if l <= heapsize and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r <= heapsize and A[r] > A[largest]:
        largest = r
    
    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(A):
    for i in range( int(math.floor(len(A)/2)), 0, -1) :
        max_heapify(A, i)

def heapsort(A):
    '''
    heapsize é usado em max_heapify
    '''
    global heapsize
    heapsize = len(A)-1
    build_max_heap(A)
    for i in range(len(A)-1, 1, -1):
        A[1], A[i] = A[i], A[1]
        heapsize = heapsize - 1
        max_heapify(A,1)


def main():
    A = [sys.maxint, 16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
    
    
    # N - dimensão do array + 1
    for N in range(1001, 10101, 500):
		tempo = 0.0
		for k in range(0,25):
			A = [ random.randint(0,100) for k in range(0, N)]
			A[0] = sys.maxint
    
			t1 = time.time()
			heapsort(A)
			A.pop(0)
			t2 = time.time()
			tempo = tempo + (t2-t1)
			pass
		tempo = tempo / 25
		
		print N-1, tempo
    
    
    #print A

main()
